Data is recorded on magnetic disks in tracks that are separated into sectors. Each sector includes a header portion that lists the sector number and other information, and a data portion in which the data are recorded. Synchronization information is also included between the sectors, so that a disk drive can determine the start of the sector and ultimately the start of the data portion of the sector.
Before recording, the data are typically encoded into data code words using an error correction code (ECC). The data code word is then recorded in the data portion of the sector. To later read the data, a disk drive moves a read/write head over the appropriate track and, using the recorded synchronization information, determines the start of the data portion of the sector of interest. The head then reads the data code word and supplies it to a decoder. The decoder reproduces the data by manipulating the code word symbols and, as necessary, correcting any errors using the ECC.
If the drive makes a mistake in determining the location of the start of the data code word, that is, if there is a synchronization error, the drive reads a portion of the data code word and either information that precedes the data code word or information that follows the data code word, depending on the direction of the synchronization error. If the decoder mistakenly interprets what is read from the disk as a valid data code word. The decoder then xe2x80x9ccorrectsxe2x80x9d what it perceives as errors in the code word, and sends the result as error-free data to an application or a user.
The ECCs that are most often used are Reed-Solomon codes. The Reed-Solomon codes encode the data over a Galois Field (2q) where xe2x80x9cqxe2x80x9d is the number of bits in a code symbol or element. The Reed-Solomon codes are cyclic. Accordingly, if c0c1 . . . cc is an unshortened code word, where the cj are elements of GF(2p), c1 . . . ccc0 is also a code word, as is ccc0c1 . . . ccxe2x88x921. This means that a synchronization error of one or more symbols may produce a different, but valid code word. If the mis-synchronization involves a number of bits rather than full symbols, the decoder most likely detects that every code word symbol is in error. Accordingly, the decoder cannot correct the errors, and labels the data as erroneous.
To protect against the misinterpretation of the symbol-sized synchronization errors, a certain prior system adds a noise-like sequence into each data code word before the code word is recorded. Using Galois Field operations, the addition is accomplished by XOR""ing the sequence and the data code word. Before decoding, the system removes the sequence by XOR""ing it to the retrieved code word. If the read operation is synchronized to the start of the codeword, that is, if there is no synchronization error, the XOR""ing of the sequence and the retrieved code word reproduces the original data code word.
Otherwise, the XOR""ing of the sequence to the retrieved code word introduces errors into the code word. Assuming the sequence is properly chosen, the decoder then detects more errors than the ECC can correct, and it labels the mis-synchronized data as erroneous. If the sequence is not properly chosen, the XOR""ing operation may instead produce a different and valid code word that can be xe2x80x9ccorrectedxe2x80x9d by the ECC.
The prior system uses a trial and error approach to finding the noise-like sequence. The trial and error approach is time consuming and does not necessarily produce a sequence that introduces a maximum number of errors into a retrieved code word that contains synchronization errors. Further, the prior systems have to store the selected sequence in the encoder, which increases the overall storage requirements of the system. Accordingly, the mis-synchronization technique may be impractical for systems that have limited storage capacities.
An error correction system produces a code word for recording by XOR""ing to a data code word that is encoded in accordance with a distance d Reed-Solomon code a coset leader that is a code word of a distance dxe2x80x2 super code of the distance d Reed-Solomon code. The coset leader is chosen such that it is not a code word of the distance d code. When the code word is later retrieved, the system XOR""s the coset leader to the retrieved code word. If there is no synchronization error, the XOR""ing operation reproduces the original data code word. If, however, there is a synchronization error, the XOR""ing operation introduces into the retrieved code word a term that is a Hamming distance of dxe2x80x2 from every valid code word of the distance d Reed-Solomon code. The result should then contain more errors than the ECC can correct, as long as       d    xe2x80x2     greater than             d      2        .  
The system determines the super code from which to select the coset leader based on the generator polynomial of the distance d Reed-Solomon code. For a code with a generator polynomial which has consecutive roots xcex1Lxcex1L+1xcex1L+2 . . . xcex1L+dxe2x88x921, where xe2x80x9cxcex1xe2x80x9d is a primitive element of GF(2q), the system first selects as the super code a distance dxe2x88x921 Reed-Solomon code with a generator polynomial that has dxe2x88x921 consecutive roots. Accordingly, the super code has a generator polynomial with roots xcex1L+1xcex1L+2 . . . xcex1L+dxe2x88x921 or roots xcex1Lxcex1L+1xcex1L+2 . . . xcex1L+dxe2x88x922. The system then selects from one of these codes a coset leader b(x) that is not also a code word of the distance d code.
The system next checks that the term j(x)=b(x)*xS+b(x) is not a valid code word of the distance d code for every S of interest, where xe2x88x92Txe2x89xa6Sxe2x89xa6T and T is the maximum number of symbols by which the read/write head may be mis-synchronized, as discussed in more detail below. If j(x), which is necessarily a code word of the distance dxe2x88x921 code, is not also a code word of the distance d code, the XOR""ing of b(x) to a retrieved code word that includes synchronization errors introduces into the code word a term that is a minimum Hamming distance of dxe2x88x921 from every valid code word of the distance d code.
If j(x) is a valid code word of the distance d code, the system selects and tests each of the remaining coset leaders from the distance dxe2x88x921 codes. If none of them are appropriate, the system selects and tests the coset leaders from a distance dxe2x88x922 Reed-Solomon code that has a generator polynomial with dxe2x88x922 consecutive roots, and so forth.
To reduce the system storage requirements, the coset leader may be selected to be a code word that contains r+1 versions of a shortened code word of the distance dxe2x80x2 code. The coset leader is thus:
bi(x)=xP*m(x)*gxe2x80x2(x)*[1+xdxe2x80x3+x2dxe2x80x3+x3dxe2x80x3+ . . . +xrdxe2x80x3]
with dxe2x80x3 greater than or equal to the degree of m(x)*gxe2x80x2(x) and p+rdxe2x80x3+dxe2x80x2xe2x88x921xe2x89xa6n, where gxe2x80x2(x) is the generator polynomial of the distance dxe2x80x2 code and n is the code length. The term m(x) may be selected to be an irreducible polynomial, and p and dxe2x80x3 are selected as discussed below. The system then stores the shortened code word rather than the entire coset leader, and XOR""s the shortened code word r+1 times to the symbols of the data code word.
The system may instead generate the coset leader by repeatedly multiplying the shortened codeword by xcex1e, and the coset leader is
bi(x)=xP*m(x)*gxe2x80x2(x)*[1+xcex1e*xdxe2x80x3+xcex12e*x2dxe2x80x3+ . . . +xcex1re*xrdxe2x80x3],
which is readily produced using a linear feedback shift register that in its initial state contains the coefficients of xP*m(x)*gxe2x80x2(x) and in each iteration multiplies the contents by xcex1e. The desirable values of r and e are such that xcex1(r+1)e=1 and the shift register thus returns to its initial state after r iterations. Otherwise, the system reloads the register to its original state after the r iterations. The shift register may instead multiply the shortened code word by arbitrary values of xcex1j, as discussed in more detail below.
The system may also generate the xe2x80x9cdataxe2x80x9d portion of the coset leader using an m-bit binary maximal length linear feedback shift register that is set to a predetermined initial condition. The system stores the associated redundancy symbols, however, to avoid having to include in the system a separate encoder for the distance dxe2x80x2 code.
Alternatively, the system may XOR the coset leader to only the redundancy symbols of the data code word, and preserve the data symbols. The selected coset leader may then be xP*gxe2x80x2(x) for p=0, 1 . . . , dxe2x88x92dxe2x80x2xe2x88x921, with the value of p chosen to xe2x80x9ccenterxe2x80x9d the coset leader over the redundancy symbols, as discussed in more detail below.